package Day2025_02_21;

public class LeetCode76 {
    public String minWindow(String s, String t) {
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();
        int n = ch1.length;
        int begin = -1;
        int minLen = n + 1;
        int kinds = ch2.length;
        int[] hash1 = new int[126];
        int[] hash2 = new int[126];
        for (char x : ch2) hash2[x]++;
        for (int left = 0, right = 0, k = 0; right < n; right++) {
            char in = ch1[right];
            if (++hash1[in] <= hash2[in]) k++;
            while (k == kinds) {
                if (minLen > right -left + 1) {
                    begin = left;
                    minLen = right - left + 1;
                }
                if (left <= right) {
                    char out = ch1[left++];
                    if (hash1[out]-- <= hash2[out]) k--;
                }
            }
        }
        return begin == -1 ? "" : s.substring(begin, begin + minLen);
    }
}
